'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-09-21 11:02:46
'''
'''
538. 把二叉搜索树转换为累加树
给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

 

例如：

输入: 原始二叉搜索树:
              5
            /   \
           2     13

输出: 转换为累加树:
             18
            /   \
          20     13
 

tips: 实际上如果拿到这个序列的逆序排列，这个就相当如将每个值改成其前缀和。只要
有个额外变量记录其前缀和即可，再将本地位置的值改成前缀和加上本值。对于BST，我们知道
传统的中序遍历就是顺序输出。如果先走右子树再走左子树，这是的中序遍历就是逆序排列。
如此，改一下这种中序遍历即可。
'''

from tree_node import *
class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        s=[0]
        def recurse(root):
            if not root:
                return
            recurse(root.right)
            root.val += s[0]
            s[0] = root.val
            # re = root.val
            recurse(root.left)
        ans = root
        recurse(root)
        return ans


if __name__ == "__main__":
    null = 'null'
    root = [1,0,4,-2,null,3]
    for i,v in enumerate(root):
        root[i] = str(v)
    s = ','.join(root)
    # print(s)
    o_s = OfficialSerialize()
    root = o_s.deserialize(s)
    solution = Solution()
    root = solution.convertBST(root)
    print(o_s.serialize(root))